/*--- APPROX.C ----------------------------- Listing 4-6 -------
 *
 * Approximate string search
 *
 * Usage:
 *  approx pattern text-to-search degree-of-approximation
 *
 *  if DRIVER is #defined, a test driver is compiled
 *-------------------------------------------------------------*/

#define DRIVER 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* local, static data */

static char *Text, *Pattern;/* pointers to search strings      */
static int Textloc;         /* current search position in Text */
static int Plen;            /* length of Pattern               */
static int Degree;          /* max degree of allowed mismatch  */
static int *Ldiff, *Rdiff;  /* dynamic difference arrays       */
static int *Loff, *Roff;    /* used to calculate start of match*/

void AppInit(char *pattern, char *text, int degree)
{
    int i;

    /* save parameters */
    Text = text;
    Pattern = pattern;
    Degree = degree;

    /* initialize */
    Plen = strlen(pattern);
    Ldiff = (int *)malloc(sizeof(int) * (Plen + 1) * 4);
    Rdiff = Ldiff + Plen + 1;
    Loff = Rdiff + Plen + 1;
    Roff = Loff +  Plen + 1;
    for (i = 0; i <= Plen; i++) {
        Rdiff[i] = i;   /* initial values for right column */
        Roff[i] = 1;
    }

    Textloc = -1;       /* current offset into Text */
}

void AppNext(char **start, char **end, int *howclose)
{
    int *temp, a, b, c, i;

    *start = NULL;
    while (*start == NULL) {/* start computing columns   */
        if (Text[++Textloc] == '\0') /* no more text     */
            break;

        temp = Rdiff;       /* move right column to left    */
        Rdiff = Ldiff;      /*  so that we can compute new  */
        Ldiff = temp;       /*  right-hand column.          */
        Rdiff[0] = 0;       /* top (boundary) row           */

        temp = Roff;        /* and swap offset arrays, too */
        Roff = Loff;
        Loff = temp;
        Roff[1] = 0;

        for (i = 0; i < Plen; i++) { /* run thru pattern  */
            /* compute a, b, & c as the 3 adjacent cells...*/
            if (Pattern[i] == Text[Textloc])
                a = Ldiff[i];
            else
                a = Ldiff[i] + 1;
            b = Ldiff[i + 1] + 1;
            c = Rdiff[i] + 1;

            /* ... now pick minimum ... */
            if (b < a)
                a = b;
            if (c < a)
                a = c;

            /* ... and store */
            Rdiff[i + 1] = a;
        }

        /*--------------------------------------------------------
         *  Now update offset array:
         *  the values in the offset arrays are added to the
         *  current location to determine the beginning of the
         *  mismatched substring. See text for details.
         *------------------------------------------------------*/
        if (Plen > 1) {
            for (i = 2; i <= Plen; i++) {
                if (Ldiff[i - 1] < Rdiff[i])
                     Roff[i] = Loff[i - 1] - 1;
                else if (Rdiff[i - 1] < Rdiff[i])
                     Roff[i] = Roff[i-1];
                else if (Ldiff[i] < Rdiff[i])
                    Roff[i] = Loff[i] - 1;
                else    /* Ldiff[i-1] == Rdiff[i] */
                    Roff[i] = Loff[i - 1] - 1;
            }
        }

		/* now, do we have an approximate match? */
        if (Rdiff[Plen] <= Degree) { /* indeed so! */
            *end = Text + Textloc;
            *start = *end + Roff[Plen];
			*howclose = Rdiff[Plen];
		}
    }

    if (start == NULL) /* all done: free dynamic arrays */
        free(Ldiff);
}

#ifdef DRIVER

int main(int argc, char *argv[])
{
    char *begin, *end;
    int howclose;

    if (argc != 4) {
        fprintf(stderr, "Usage is: approx pattern text degree\n");
        return (EXIT_FAILURE);
    }

    AppInit(argv[1], argv[2], atoi(argv[3]));
    AppNext(&begin, &end, &howclose);

    while (begin != NULL) {
        printf("Degree %d: %.*s\n",
               howclose, end-begin + 1, begin);
        AppNext(&begin, &end, &howclose);
    }

    return (EXIT_SUCCESS);
}
#endif
